package com.desheng.bigdata.ds.link;

/**
 * @Description 循环链表处理约瑟夫问题
 *     据说著名犹太历史学家Josephus有过以下的故事：
 *        在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，
 *        于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重
 *        新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第
 *        一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只
 *        剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的
 *        朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
 * @Author deshenglijun
 * @Date 2020/5/12 22:49
 * @Version 1.0
 */
public class LoopLink2Joseph {
    public static void main(String[] args) {

        Node<Integer> first = null;
        Node<Integer> previous = null;
        int size = 41;
        for(int i = 1; i <= size; i++) {
            //第一个节点
            if(i == 1) {
                first = new Node<>(i,null);
                previous = first;
                continue;
            }
            //其它普通节点
            Node<Integer> newNode = new Node<>(i, null);
            previous.next = newNode;
            previous = newNode;//当前节点，是下一次节点的上一个节点

            if(i == size) {
                newNode.next = first; //最后一个节点的下一个节点是第一个节点
            }
        }

        joseph(first);

    }

    private static <E> void joseph(Node<E> first) {
        //计数器 模拟报数
        int count = 0;
        Node<E> currentNode = first; //当前节点
        Node<E> before = first; //上一个节点，这里定义上一个节点的束腰原因在于为了删除当前节点而使用

        while(currentNode != currentNode.next) {
            count++;
            if(count == 3) { //报数为3，重置计数器，并且删除当前的节点
                before.next = currentNode.next;
                count = 0;
                System.out.print(currentNode.data + "\t");
            } else {//如果不是，则让上一个节点指向当前节点，成为下一次遍历是节点的上一个节点
                before = currentNode;
            }
            currentNode = currentNode.next;
        }

        System.out.println(currentNode.data);
    }


    static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }
}
